/**
 * 
 */
package gpl.scotlandyard.services;

import gpl.scotlandyard.beans.MarkedNode;
import gpl.scotlandyard.beans.basics.Board;
import gpl.scotlandyard.beans.basics.Link;
import gpl.scotlandyard.beans.basics.Node;
import gpl.scotlandyard.beans.basics.Player;
import gpl.scotlandyard.beans.basics.Ticket;
import gpl.scotlandyard.exceptions.InvalidUserInputException;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import org.apache.log4j.Logger;

/** @author norbert */
public class PathFinder {

  private static final Logger LOG = Logger.getLogger(PathFinder.class);
  private final Board board;
  private final MoveTracker fugitiveTracker;
  private final List<MoveTracker> detectiveTrackers = new ArrayList<MoveTracker>();
  private final List<PathFinder.Listener> listeners = new ArrayList<PathFinder.Listener>();
  private final FreePlayerManager playerMgr = new FreePlayerManager();
  private HashMap<Player, List<Node>> nextDetectives = new HashMap<Player, List<Node>>();
  private List<Node> nextFugitive = new LinkedList<Node>();
  private final List<List<Node>> freeNodes = new ArrayList<List<Node>>();
  private final List<List<Node>> safePaths = new ArrayList<List<Node>>();

  /** @param b */
  public PathFinder(Board b) {
    board = b;
    fugitiveTracker = new MoveTracker(board.getFugitive());
    for (Player detective : board.getDetectives()) {
      detectiveTrackers.add(new MoveTracker(detective));
    }
  }

  /**
   * Performs discover of safe paths.
   * 
   * @return List of longest safe paths
   */
  public void performDiscover() {
    // init first next position is current position
    nextFugitive.clear();
    nextDetectives.clear();
    freeNodes.clear();
    safePaths.clear();
    nextFugitive = Collections.singletonList(fugitiveTracker.getPlayer().getNode());
    for (MoveTracker tracker : detectiveTrackers) {
      nextDetectives.put(tracker.getPlayer(), Collections.singletonList(tracker.getPlayer().getNode()));
    }

    // perform
    for (int nbTurn = 1; nbTurn <= Board.MAX_TURN; nbTurn++) {
      performTurn(nbTurn);
      if (nextFugitive.size() == 0) {
        break;
      } else {
        freeNodes.add(new ArrayList<Node>(nextFugitive));
        LOG.debug("#" + nbTurn + " fugitive safe next nodes : " + nextFugitive);
      }
    }
    LOG.info("longest safe paths : " + freeNodes.size());

    // build result
    buildSafePaths();
    LOG.info("safe paths : " + safePaths);
    fireUpdated();
  }

  /**
   * Longest paths first
   * 
   * @return safe path comparator
   */
  private Comparator<List<Node>> getSafePathsComparator() {
    return new Comparator<List<Node>>() {
      @Override
      public int compare(List<Node> o1, List<Node> o2) {
        if (o1.size() == o2.size()) {
          return o1.toString().compareTo(o2.toString());
        }
        return (o1.size() - o2.size()) * -1;
      }
    };
  }

  /**
   * Clears old safe paths and list complete paths based on free nodes at each turn.
   */
  private void buildSafePaths() {
    safePaths.clear();
    int range = freeNodes.size() - 1;
    if (range >= 0) {
      for (Node node : freeNodes.get(range)) {
        for (List<Node> prevList : getPrevious(range, node)) {
          safePaths.add(new ArrayList<Node>(prevList));
        }
      }
    }
    LOG.debug("buildSafePaths finished");
  }

  /**
   * List of different paths that lead to this node. The first item of the sublist is the start node.
   * 
   * @param currentRange
   * @param node
   * @return full path to this node
   */
  private List<List<Node>> getPrevious(int currentRange, Node node) {
    List<List<Node>> paths = new ArrayList<List<Node>>();
    if (currentRange == 0) {
      paths.add(Collections.singletonList(node));
      return paths;
    }
    // find linked previous nodes
    Set<Node> prevNodes = new HashSet<Node>();
    for (Node prev : freeNodes.get(currentRange - 1)) {
      for (Link prevLink : prev.getLinks()) {
        if (prevLink.getToNode().equals(node)) {
          prevNodes.add(prev);
        }
      }
    }
    // get previous of these and create full path
    for (Node prev : prevNodes) {
      for (List<Node> prevList : getPrevious(currentRange - 1, prev)) {
        List<Node> path = new ArrayList<Node>();
        path.addAll(prevList);
        path.add(node);
        paths.add(path);
      }
    }

    return paths;
  }

  /** @param x */
  private void performTurn(int x) {
    LOG.debug("---- performTurn " + x + " ----");
    fugitiveTracker.setPossiblePositions(nextFugitive);
    for (MoveTracker mt : detectiveTrackers) {
      mt.setPossiblePositions(nextDetectives.get(mt.getPlayer()));
    }
    calcFugitiveNextSafePosition();
  }

  /**
   * Begins by {@link #caclDetectiveNextPositions()} then perform comparison with fugitive potential moves and keeps only safe destinations.
   * Result stored in {@link #nextFugitive}.
   */
  private void calcFugitiveNextSafePosition() {
    caclDetectiveNextPositions();
    Player playerClone = fugitiveTracker.getPlayer().clone();
    List<Link> fugPotentialMoves = new LinkedList<Link>();
    for (MarkedNode possibleNode : fugitiveTracker.getPossiblePositions()) {
      playerClone.setNode(possibleNode.getNode());
      fugPotentialMoves.addAll(playerMgr.getMoves(playerClone));
    }

    // keep only destination nodes
    List<Node> fugNodes = new ArrayList<Node>();
    for (Link link : fugPotentialMoves) {
      if (!fugNodes.contains(link.getToNode())) {
        fugNodes.add(link.getToNode());
      }
    }
    LOG.info("fugitive potential next nodes [" + fugNodes.size() + "] : " + fugNodes);

    // remove impossible nodes cause already busied
    HashSet<Node> toDel = new HashSet<Node>();
    for (MoveTracker tracker : detectiveTrackers) {
      for (Node nd : fugNodes) {
        if (nd.equals(tracker.getPlayer().getNode())) {
          toDel.add(nd);
        }
      }
    }
    LOG.info("current busied nodes to del [" + toDel.size() + "] : " + toDel);
    fugNodes.removeAll(toDel);

    // remove next potential busied nodes
    toDel.clear();
    for (List<Node> list : nextDetectives.values()) {
      for (Node nd : list) {
        if (fugNodes.contains(nd)) {
          toDel.add(nd);
        }
      }
    }
    LOG.info("next unsafe nodes to del [" + toDel.size() + "]: " + toDel);
    fugNodes.removeAll(toDel);

    // keep safe moves
    LOG.info("fugitive safe next nodes [" + fugNodes.size() + "] : " + fugNodes);
    nextFugitive = fugNodes;
  }

  /** Results stored in {@link #nextDetectives}. */
  private void caclDetectiveNextPositions() {
    nextDetectives = new HashMap<Player, List<Node>>();
    for (MoveTracker tracker : detectiveTrackers) {
      List<Node> nexts = new ArrayList<Node>();
      Player playerClone = tracker.getPlayer().clone();
      for (MarkedNode currNode : tracker.getPossiblePositions()) {
        playerMgr.move(playerClone, new Link(currNode.getNode(), currNode.getNode(), Ticket.HIDE));
        for (Link nextMoves : playerMgr.getMoves(playerClone)) {
          if (!nexts.contains(nextMoves.getToNode())) {
            nexts.add(nextMoves.getToNode());
          }
        }
      }
      nextDetectives.put(tracker.getPlayer(), nexts);
    }
  }

  /**
   * @param fugPos
   * @param detPos
   * @throws InvalidUserInputException
   */
  public void setPlayersPositions(int fugPos, List<Integer> detPos) throws InvalidUserInputException {
    if (detPos.size() != detectiveTrackers.size()) {
      throw new InvalidUserInputException("detPos has not same size that tracked detectives");
    }
    Node n = board.getMap().get(fugPos - 1);
    playerMgr.move(fugitiveTracker.getPlayer(), new Link(n, n, Ticket.HIDE));

    int i = 0;
    for (Integer pos : detPos) {
      n = board.getMap().get(pos - 1);
      playerMgr.move(detectiveTrackers.get(i).getPlayer(), new Link(n, n, Ticket.HIDE));
      i++;
    }
  }

  /**
   * Returns the size of longest safe path.
   * 
   * @return size
   */
  public int getLongestSafePathLength() {
    if (safePaths.size() == 0) {
      return 0;
    }
    return safePaths.get(0).size();
  }

  /**
   * Returns the number of longest safe paths.
   * 
   * @return number
   */
  public int getLongestSafePathsCount() {
    return safePaths.size();
  }

  /**
   * Returns the safe paths.
   * 
   * @return paths
   */
  public List<List<Node>> getSafePaths() {
    return Collections.unmodifiableList(safePaths);
  }

  /** @param listener */
  public void addListener(PathFinder.Listener listener) {
    listeners.add(listener);
  }

  /** @param listener */
  public void removeListener(PathFinder.Listener listener) {
    listeners.remove(listener);
  }

  /**
   * 
   */
  private void fireUpdated() {

    Collections.sort(safePaths, getSafePathsComparator());
    for (PathFinder.Listener listener : listeners) {
      listener.updated();
    }
  }

  /** @author norbert */
  public interface Listener {
    /**
     * 
     */
    void updated();
  }

  /** @author norbert */
  public static class ListenerImpl implements Listener {

    @Override
    public void updated() {
      // does nothing
    }
  }

}
